package com.mzy.linear_struct.hot100.二叉树;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/20/上午12:10
 * @Description:
 */
public class Pro106从中序与后序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        // 1. 先找根节点，也就是后续的最后一个节点
        // 2. 切割左右节点
        // 2.1 如果左节点为一个元素，直接添加到二叉树中，否则进行递归添加
        // 2.2 如果右节点为一个元素，直接...
        // 递归步骤，从第一步继续开始

        TreeNode tree;
        tree = build(inorder, postorder);

        return tree;

    }

    private TreeNode build(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }
        if (postorder.length == 1) {
            return new TreeNode(postorder[0]);
        }

        int root = postorder[postorder.length - 1];
        // 跟节点左边的就是左子树，右边的就是右子树
        TreeNode tree = new TreeNode(root);

        int rootIndex = 0;
        // 找到中序遍历数组中的根节点
        while (inorder[rootIndex] != root) {
            rootIndex++;
        }

        // 9 3  15 20 7 中序
        // 9 15 7  20 3 后序
        // 切割左中序
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, rootIndex);
        // 切割右中序
        int[] inorderRight = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
        // 左后续 的位置怎么获取 -> 中序的根节点的前一个元素就是左后续

        // 切割左后续，左后续的起始位置都是0，结束位置是左中序中元素的个数
        int[] postorderLeft = Arrays.copyOfRange(postorder, 0, inorderLeft.length);

        // 切割右后续，右后续的起始位置为【左中序的元素个数】，结束位置后续遍历的数组，最后一个元素不要
        int[] postorderRight = Arrays.copyOfRange(postorder, inorderLeft.length, postorder.length - 1);

        tree.left = build(inorderLeft, postorderLeft);
        tree.right = build(inorderRight, postorderRight);
        return tree;
    }

    public static void main(String[] args) {
        TreeNode tree = new Pro106从中序与后序遍历序列构造二叉树().buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        tree = new Pro106从中序与后序遍历序列构造二叉树().buildTree(new int[]{2, 1}, new int[]{2, 1});
        tree = new Pro106从中序与后序遍历序列构造二叉树().buildTree(new int[]{1, 3, 2}, new int[]{3, 2, 1});
        tree = new Pro106从中序与后序遍历序列构造二叉树().buildTree(new int[]{3, 2, 1}, new int[]{3, 2, 1});
        System.out.println(tree);
    }

}
